package 递归.插入排序;

public class Test {
    public static void sort(int[] a) {
        insertion(a, 1);
    }

    // 第一类
    private static void insertion(int[] a, int low) {
        if (low == a.length) {
            return;
        }
        int t = a[low];
        int i = low - 1;
        while (i >= 0 && a[i] > t) {
            a[low] = a[i];
            i--;
        }
        a[i + 1] = t;
        insertion(a, low + 1);
    }

    // 第二类
    private static void insertion2(int[] a, int low) {
        if (low == a.length) {
            return;
        }
        int i = low - 1;
        while (i >= 0 && a[i] > a[i + 1]) {
            int t = a[i];
            a[i] = a[i + 1];
            a[i + 1] = t;
            i--;
        }
        insertion2(a, low + 1);
    }
}
